ebab7d0da53c51438720d60c6e2e467c - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Surjective function</title>

</head>

Surjective function

</h1>

</header>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hatnote{font-style:italic}.mw-parser-output div.hatnote{padding-left:1.6em;margin-bottom:0.5em}.mw-parser-output .hatnote i{font-style:normal}.mw-parser-output .hatnote+link+.hatnote{margin-top:-0.5em}@media print{body.ns-0 .mw-parser-output .hatnote{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div role="note" class="hatnote navigation-not-searchable">"Onto" redirects here. For other uses, see <a href="https://en.wiktionary.org/wiki/onto" class="extiw external" title="wiktionary:onto">wiktionary:onto</a>.</div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hlist dl,.mw-parser-output .hlist ol,.mw-parser-output .hlist ul{margin:0;padding:0}.mw-parser-output .hlist dd,.mw-parser-output .hlist dt,.mw-parser-output .hlist li{margin:0;display:inline}.mw-parser-output .hlist.inline,.mw-parser-output .hlist.inline dl,.mw-parser-output .hlist.inline ol,.mw-parser-output .hlist.inline ul,.mw-parser-output .hlist dl dl,.mw-parser-output .hlist dl ol,.mw-parser-output .hlist dl ul,.mw-parser-output .hlist ol dl,.mw-parser-output .hlist ol ol,.mw-parser-output .hlist ol ul,.mw-parser-output .hlist ul dl,.mw-parser-output .hlist ul ol,.mw-parser-output .hlist ul ul{display:inline}.mw-parser-output .hlist .mw-empty-li{display:none}.mw-parser-output .hlist dt::after{content:": "}.mw-parser-output .hlist dd::after,.mw-parser-output .hlist li::after{content:" · ";font-weight:bold}.mw-parser-output .hlist dd:last-child::after,.mw-parser-output .hlist dt:last-child::after,.mw-parser-output .hlist li:last-child::after{content:none}.mw-parser-output .hlist dd dd:first-child::before,.mw-parser-output .hlist dd dt:first-child::before,.mw-parser-output .hlist dd li:first-child::before,.mw-parser-output .hlist dt dd:first-child::before,.mw-parser-output .hlist dt dt:first-child::before,.mw-parser-output .hlist dt li:first-child::before,.mw-parser-output .hlist li dd:first-child::before,.mw-parser-output .hlist li dt:first-child::before,.mw-parser-output .hlist li li:first-child::before{content:" (";font-weight:normal}.mw-parser-output .hlist dd dd:last-child::after,.mw-parser-output .hlist dd dt:last-child::after,.mw-parser-output .hlist dd li:last-child::after,.mw-parser-output .hlist dt dd:last-child::after,.mw-parser-output .hlist dt dt:last-child::after,.mw-parser-output .hlist dt li:last-child::after,.mw-parser-output .hlist li dd:last-child::after,.mw-parser-output .hlist li dt:last-child::after,.mw-parser-output .hlist li li:last-child::after{content:")";font-weight:normal}.mw-parser-output .hlist ol{counter-reset:listitem}.mw-parser-output .hlist ol>li{counter-increment:listitem}.mw-parser-output .hlist ol>li::before{content:" "counter(listitem)"\a0 "}.mw-parser-output .hlist dd ol>li:first-child::before,.mw-parser-output .hlist dt ol>li:first-child::before,.mw-parser-output .hlist li ol>li:first-child::before{content:" ("counter(listitem)"\a0 "}

/* end https://en.wikipedia.org/ */

</style><style data-mw-deduplicate="TemplateStyles:r1246091330">

/* start https://en.wikipedia.org/ */

.mw-parser-output .sidebar{width:22em;float:right;clear:right;margin:0.5em 0 1em 1em;background:var(--background-color-neutral-subtle,#f8f9fa);border:1px solid var(--border-color-base,#a2a9b1);padding:0.2em;text-align:center;line-height:1.4em;font-size:88%;border-collapse:collapse;display:table}body.skin-minerva .mw-parser-output .sidebar{display:table!important;float:right!important;margin:0.5em 0 1em 1em!important}.mw-parser-output .sidebar-subgroup{width:100%;margin:0;border-spacing:0}.mw-parser-output .sidebar-left{float:left;clear:left;margin:0.5em 1em 1em 0}.mw-parser-output .sidebar-none{float:none;clear:both;margin:0.5em 1em 1em 0}.mw-parser-output .sidebar-outer-title{padding:0 0.4em 0.2em;font-size:125%;line-height:1.2em;font-weight:bold}.mw-parser-output .sidebar-top-image{padding:0.4em}.mw-parser-output .sidebar-top-caption,.mw-parser-output .sidebar-pretitle-with-top-image,.mw-parser-output .sidebar-caption{padding:0.2em 0.4em 0;line-height:1.2em}.mw-parser-output .sidebar-pretitle{padding:0.4em 0.4em 0;line-height:1.2em}.mw-parser-output .sidebar-title,.mw-parser-output .sidebar-title-with-pretitle{padding:0.2em 0.8em;font-size:145%;line-height:1.2em}.mw-parser-output .sidebar-title-with-pretitle{padding:0.1em 0.4em}.mw-parser-output .sidebar-image{padding:0.2em 0.4em 0.4em}.mw-parser-output .sidebar-heading{padding:0.1em 0.4em}.mw-parser-output .sidebar-content{padding:0 0.5em 0.4em}.mw-parser-output .sidebar-content-with-subgroup{padding:0.1em 0.4em 0.2em}.mw-parser-output .sidebar-above,.mw-parser-output .sidebar-below{padding:0.3em 0.8em;font-weight:bold}.mw-parser-output .sidebar-collapse .sidebar-above,.mw-parser-output .sidebar-collapse .sidebar-below{border-top:1px solid #aaa;border-bottom:1px solid #aaa}.mw-parser-output .sidebar-navbar{text-align:right;font-size:115%;padding:0 0.4em 0.4em}.mw-parser-output .sidebar-list-title{padding:0 0.4em;text-align:left;font-weight:bold;line-height:1.6em;font-size:105%}.mw-parser-output .sidebar-list-title-c{padding:0 0.4em;text-align:center;margin:0 3.3em}@media(max-width:640px){body.mediawiki .mw-parser-output .sidebar{width:100%!important;clear:both;float:none!important;margin-left:0!important;margin-right:0!important}}body.skin--responsive .mw-parser-output .sidebar a>img{max-width:none!important}@media screen{html.skin-theme-clientpref-night .mw-parser-output .sidebar:not(.notheme) .sidebar-list-title,html.skin-theme-clientpref-night .mw-parser-output .sidebar:not(.notheme) .sidebar-title-with-pretitle{background:transparent!important}html.skin-theme-clientpref-night .mw-parser-output .sidebar:not(.notheme) .sidebar-title-with-pretitle a{color:var(--color-progressive)!important}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .sidebar:not(.notheme) .sidebar-list-title,html.skin-theme-clientpref-os .mw-parser-output .sidebar:not(.notheme) .sidebar-title-with-pretitle{background:transparent!important}html.skin-theme-clientpref-os .mw-parser-output .sidebar:not(.notheme) .sidebar-title-with-pretitle a{color:var(--color-progressive)!important}}@media print{body.ns-0 .mw-parser-output .sidebar{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><table class="sidebar nomobile nowraplinks"><tbody><tr><th class="sidebar-title" style="letter-spacing:0.0125em; background-color:#FFCC99"><a href="Function_(mathematics)" title="Function (mathematics)">Function</a></th></tr><tr><td class="sidebar-image">x ↦ f (x)</td></tr><tr><th class="sidebar-heading" style="font-size: 117%; letter-spacing: 0.0125em; font-weight: 500; border-top: 1px solid black; padding: 5px 0 3px">

<a href="History_of_the_function_concept" title="History of the function concept">History of the function concept</a></th></tr><tr><th class="sidebar-heading" style="font-size: 117%; letter-spacing: 0.0125em; font-weight: 500; border-top: 1px solid black; padding: 5px 0 3px">

Types by <a href="Domain_of_a_function" title="Domain of a function">domain</a> and <a href="Codomain" title="Codomain">codomain</a></th></tr><tr><td class="sidebar-content">

𝔹

→ <var>X</var></a></li>

𝔹<var>n</var>

→ <var>X</var></a></li>

→ ℤ</a></li>

ℤ

→ <var>X</var></a></li>

→ ℝ</a></li>

ℝ

→ <var>X</var></a></li>

ℝ<var>n</var>

→ <var>X</var></a></li>

→ ℂ</a></li>

ℂ

→ <var>X</var></a></li>

ℂ<var>n</var>

→ <var>X</var></a></li></ul>

</div></td>

</tr><tr><th class="sidebar-heading" style="font-size: 117%; letter-spacing: 0.0125em; font-weight: 500; border-top: 1px solid black; padding: 5px 0 3px">

<a href="List_of_types_of_functions" title="List of types of functions">Classes/properties</a> </th></tr><tr><td class="sidebar-content">

<ul><li><a href="Constant_function" title="Constant function">Constant</a></li>

<li><a href="Identity_function" title="Identity function">Identity</a></li>

<li><a href="Linear_map" title="Linear map">Linear</a></li>

<li><a href="Polynomial" title="Polynomial">Polynomial</a></li>

<li><a href="Rational_function" title="Rational function">Rational</a></li>

<li><a href="Algebraic_function" title="Algebraic function">Algebraic</a></li>

<li><a href="Analytic_function" title="Analytic function">Analytic</a></li>

<li><a href="Smooth_function" class="mw-redirect" title="Smooth function">Smooth</a></li>

<li><a href="Continuous_function" title="Continuous function">Continuous</a></li>

<li><a href="Measurable_function" title="Measurable function">Measurable</a></li>

<li><a href="Injective_function" title="Injective function">Injective</a></li>

<li><a href="Bijection" title="Bijection">Bijective</a></li></ul>

</div></td>

</tr><tr><th class="sidebar-heading" style="font-size: 117%; letter-spacing: 0.0125em; font-weight: 500; border-top: 1px solid black; padding: 5px 0 3px">

Constructions</th></tr><tr><td class="sidebar-content">

<ul><li><a href="Restriction_(mathematics)" title="Restriction (mathematics)">Restriction</a></li>

<li><a href="Function_composition" title="Function composition">Composition</a></li>

<li><a href="Inverse_function" title="Inverse function">Inverse</a></li></ul>

</div></td>

</tr><tr><th class="sidebar-heading" style="font-size: 117%; letter-spacing: 0.0125em; font-weight: 500; border-top: 1px solid black; padding: 5px 0 3px">

Generalizations </th></tr><tr><td class="sidebar-content">

<ul><li><a href="Relation_(mathematics)" title="Relation (mathematics)">Relation</a> (<a href="Binary_relation" title="Binary relation">Binary relation</a>)</li>

<li><a href="Set-valued_function" title="Set-valued function">Set-valued</a></li>

<li><a href="Multivalued_function" title="Multivalued function">Multivalued</a></li>

<li><a href="Partial_function" title="Partial function">Partial</a></li>

<li><a href="Implicit_function" title="Implicit function">Implicit</a></li>

<li><a href="Function_space" title="Function space">Space</a></li>

<li><a href="Higher-order_function" title="Higher-order function">Higher-order</a></li>

<li><a href="Morphism" title="Morphism">Morphism</a></li>

<li><a href="Functor" title="Functor">Functor</a></li></ul>

</div></td>

</tr><tr><th class="sidebar-heading" style="font-size: 117%; letter-spacing: 0.0125em; font-weight: 500; border-top: 1px solid black; padding: 5px 0 3px">

<a href="List_of_mathematical_functions" title="List of mathematical functions">List of specific functions</a></th></tr><tr><td class="sidebar-navbar"><style data-mw-deduplicate="TemplateStyles:r1239400231">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbar{display:inline;font-size:88%;font-weight:normal}.mw-parser-output .navbar-collapse{float:left;text-align:left}.mw-parser-output .navbar-boxtext{word-spacing:0}.mw-parser-output .navbar ul{display:inline-block;white-space:nowrap;line-height:inherit}.mw-parser-output .navbar-brackets::before{margin-right:-0.125em;content:"[ "}.mw-parser-output .navbar-brackets::after{margin-left:-0.125em;content:" ]"}.mw-parser-output .navbar li{word-spacing:-0.125em}.mw-parser-output .navbar a>span,.mw-parser-output .navbar a>abbr{text-decoration:inherit}.mw-parser-output .navbar-mini abbr{font-variant:small-caps;border-bottom:none;text-decoration:none;cursor:inherit}.mw-parser-output .navbar-ct-full{font-size:114%;margin:0 7em}.mw-parser-output .navbar-ct-mini{font-size:114%;margin:0 4em}html.skin-theme-clientpref-night .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}@media(prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}}@media print{.mw-parser-output .navbar{display:none!important}}

/* end https://en.wikipedia.org/ */

</style></td></tr></tbody></table>

In <a href="Mathematics" title="Mathematics">mathematics</a>, a surjective function (also known as surjection, or onto function /ˈɒn.tuː/) is a <a href="Function_(mathematics)" title="Function (mathematics)">function</a> f such that, for every element y of the function's <a href="Codomain" title="Codomain">codomain</a>, there exists at least one element x in the function's <a href="Domain_of_a_function" title="Domain of a function">domain</a> such that f(x) = y. In other words, for a function f : X → Y, the codomain Y is the <a href="Image_(mathematics)" title="Image (mathematics)">image</a> of the function's domain X.<a href="#cite_note-:0-1">[1]</a><a href="#cite_note-:1-2">[2]</a> It is not required that x be <a href="Unique_(mathematics)" class="mw-redirect" title="Unique (mathematics)">unique</a>; the function f may map one or more elements of X to the same element of Y.

The term surjective and the related terms <a href="Injective_function" title="Injective function">injective</a> and <a href="Bijective_function" class="mw-redirect" title="Bijective function">bijective</a> were introduced by <a href="Nicolas_Bourbaki" title="Nicolas Bourbaki">Nicolas Bourbaki</a>,<a href="#cite_note-3">[3]</a><a href="#cite_note-4">[4]</a> a group of mainly <a href="France" title="France">French</a> 20th-century <a href="Mathematician" title="Mathematician">mathematicians</a> who, under this pseudonym, wrote a series of books presenting an exposition of modern advanced mathematics, beginning in 1935. The French word <a href="https://en.wiktionary.org/wiki/sur#French" class="extiw external" title="wikt:sur">sur</a> means over or above, and relates to the fact that the <a href="Image_(mathematics)" title="Image (mathematics)">image</a> of the domain of a surjective function completely covers the function's codomain.

Any function induces a surjection by <a href="Restriction_of_a_function" class="mw-redirect" title="Restriction of a function">restricting</a> its codomain to the image of its domain. Every surjective function has a <a href="Inverse_function#Left_and_right_inverses" title="Inverse function">right inverse</a> assuming the <a href="Axiom_of_choice" title="Axiom of choice">axiom of choice</a>, and every function with a right inverse is necessarily a surjection. The <a href="Function_composition" title="Function composition">composition</a> of surjective functions is always surjective. Any function can be decomposed into a surjection and an injection.

<div class="mw-heading mw-heading2"><h2 id="Definition">Definition</h2></div>

<div role="note" class="hatnote navigation-not-searchable">Further information on notation: <a href="Function_(mathematics)#Notation" title="Function (mathematics)">Function (mathematics) § Notation</a></div>

A surjective function is a <a href="Function_(mathematics)" title="Function (mathematics)">function</a> whose <a href="Image_(mathematics)" title="Image (mathematics)">image</a> is equal to its <a href="Codomain" title="Codomain">codomain</a>. Equivalently, a function <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f}</annotation>

</semantics>

</math><img src="./132e57acb643253e7810ee9702d9581f159a1c61.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.279ex; height:2.509ex;" alt="{\displaystyle f}" loading="lazy"> with <a href="Domain_of_a_function" title="Domain of a function">domain</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X}</annotation>

</semantics>

</math><img src="./68baa052181f707c662844a465bfeeb135e82bab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.98ex; height:2.176ex;" alt="{\displaystyle X}" loading="lazy"> and codomain <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Y}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Y}</annotation>

</semantics>

</math><img src="./961d67d6b454b4df2301ac571808a3538b3a6d3f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.171ex; width:1.773ex; height:2.009ex;" alt="{\displaystyle Y}" loading="lazy"> is surjective if for every <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y}</annotation>

</semantics>

</math><img src="./b8a6208ec717213d4317e666f1ae872e00620a0d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.155ex; height:2.009ex;" alt="{\displaystyle y}" loading="lazy"> in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Y}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Y}</annotation>

</semantics>

</math><img src="./961d67d6b454b4df2301ac571808a3538b3a6d3f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.171ex; width:1.773ex; height:2.009ex;" alt="{\displaystyle Y}" loading="lazy"> there exists at least one <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math><img src="./87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy"> in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X}</annotation>

</semantics>

</math><img src="./68baa052181f707c662844a465bfeeb135e82bab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.98ex; height:2.176ex;" alt="{\displaystyle X}" loading="lazy"> with <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(x)=y}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(x)=y}</annotation>

</semantics>

</math><img src="./0a5080a8b0a963407ea74ffa50702563771518d1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.672ex; height:2.843ex;" alt="{\displaystyle f(x)=y}" loading="lazy">.<a href="#cite_note-:0-1">[1]</a> Surjections are sometimes denoted by a two-headed rightwards arrow (<style data-mw-deduplicate="TemplateStyles:r886049734">

/* start https://en.wikipedia.org/ */

.mw-parser-output .monospaced{font-family:monospace,monospace}

/* end https://en.wikipedia.org/ */

</style><a href="Unicode" title="Unicode">U+</a>21A0 ↠ RIGHTWARDS TWO HEADED ARROW),<a href="#cite_note-Unicode_Arrows-5">[5]</a> as in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f\colon X\twoheadrightarrow Y}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f\colon X\twoheadrightarrow Y}</annotation>

</semantics>

</math><img src="./245f8c3c6bf7968f9dbdbeda676e959e08870d50.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:9.68ex; height:2.509ex;" alt="{\displaystyle f\colon X\twoheadrightarrow Y}" loading="lazy">.

Symbolically,

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f\colon X\rightarrow Y}</annotation>

</semantics>

</math><img src="./6f986e95e93b70de25a0084daf075cb02c3ccae8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:9.68ex; height:2.509ex;" alt="{\displaystyle f\colon X\rightarrow Y}" loading="lazy">, then <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f}</annotation>

</semantics>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \forall y\in Y,\,\exists x\in X,\;\;f(x)=y}</annotation>

</semantics>

</math><img src="./a1c33ca492c6a0392d37a336f8fdca8722522e2c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:26.922ex; height:2.843ex;" alt="{\displaystyle \forall y\in Y,\,\exists x\in X,\;\;f(x)=y}" loading="lazy">.<a href="#cite_note-:1-2">[2]</a><a href="#cite_note-6">[6]</a></dd></dl>

<div class="mw-heading mw-heading2"><h2 id="Examples">Examples</h2></div>

<div role="note" class="hatnote navigation-not-searchable">For more examples, see <a href="#Gallery">§ Gallery</a>.</div>

<ul><li>For any set X, the <a href="Identity_function" title="Identity function">identity function</a> idX on X is surjective.</li>

<li>The function f : Z → {0, 1} defined by f(n) = n <a href="Modular_arithmetic" title="Modular arithmetic">mod</a> 2 (that is, <a href="Even_number" class="mw-redirect" title="Even number">even</a> <a href="Integer" title="Integer">integers</a> are mapped to 0 and <a href="Odd_number" class="mw-redirect" title="Odd number">odd</a> integers to 1) is surjective.</li>

<li>The function f : R → R defined by f(x) = 2x + 1 is surjective (and even <a href="Bijective_function" class="mw-redirect" title="Bijective function">bijective</a>), because for every <a href="Real_number" title="Real number">real number</a> y, we have an x such that f(x) = y: such an appropriate x is (y − 1)/2.</li>

<li>The function f : R → R defined by f(x) = x3 − 3x is surjective, because the pre-image of any <a href="Real_number" title="Real number">real number</a> y is the solution set of the cubic polynomial equation x3 − 3x − y = 0, and every cubic polynomial with real coefficients has at least one real root. However, this function is not <a href="Injective_function" title="Injective function">injective</a> (and hence not <a href="Bijective_function" class="mw-redirect" title="Bijective function">bijective</a>), since, for example, the pre-image of y = 2 is {x = −1, x = 2}. (In fact, the pre-image of this function for every y, −2 ≤ y ≤ 2 has more than one element.)</li>

<li>The function g : R → R defined by g(x) = x2 is not surjective, since there is no real number x such that x2 = −1. However, the function g : R → R≥0 defined by g(x) = x2 (with the restricted codomain) is surjective, since for every y in the nonnegative real codomain Y, there is at least one x in the real domain X such that x2 = y.</li>

<li>The <a href="Natural_logarithm" title="Natural logarithm">natural logarithm</a> function ln : (0, +∞) → R is a surjective and even bijective (mapping from the set of positive real numbers to the set of all real numbers). Its inverse, the <a href="Exponential_function" title="Exponential function">exponential function</a>, if defined with the set of real numbers as the domain and the codomain, is not surjective (as its range is the set of positive real numbers).</li>

<li>The <a href="Matrix_exponential" title="Matrix exponential">matrix exponential</a> is not surjective when seen as a map from the space of all n×n <a href="Matrix_(mathematics)" title="Matrix (mathematics)">matrices</a> to itself. It is, however, usually defined as a map from the space of all n×n matrices to the <a href="General_linear_group" title="General linear group">general linear group</a> of degree n (that is, the <a href="Group_(mathematics)" title="Group (mathematics)">group</a> of all n×n <a href="Invertible_matrix" title="Invertible matrix">invertible matrices</a>). Under this definition, the matrix exponential is surjective for complex matrices, although still not surjective for real matrices.</li>

<li>The <a href="Projection_(set_theory)" title="Projection (set theory)">projection</a> from a <a href="Cartesian_product" title="Cartesian product">cartesian product</a> A × B to one of its factors is surjective, unless the other factor is empty.</li>

<li>In a 3D video game, vectors are projected onto a 2D flat screen by means of a surjective function.</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Properties">Properties</h2></div>

A function is <a href="Bijective_function" class="mw-redirect" title="Bijective function">bijective</a> if and only if it is both surjective and <a href="Injective_function" title="Injective function">injective</a>.

If (as is often done) a function is identified with its <a href="Graph_of_a_function" title="Graph of a function">graph</a>, then surjectivity is not a property of the function itself, but rather a property of the <a href="Map_(mathematics)" title="Map (mathematics)">mapping</a>.<a href="#cite_note-7">[7]</a> This is, the function together with its codomain. Unlike injectivity, surjectivity cannot be read off of the graph of the function alone.

<div class="mw-heading mw-heading3"><h3 id="Surjections_as_right_invertible_functions">Surjections as right invertible functions</h3></div>

The function g : Y → X is said to be a <a href="Inverse_function#Left_and_right_inverses" title="Inverse function">right inverse</a> of the function f : X → Y if f(g(y)) = y for every y in Y (g can be undone by f). In other words, g is a right inverse of f if the <a href="Function_composition" title="Function composition">composition</a> f o g of g and f in that order is the <a href="Identity_function" title="Identity function">identity function</a> on the domain Y of g. The function g need not be a complete <a href="Inverse_function" title="Inverse function">inverse</a> of f because the composition in the other order, g o f, may not be the identity function on the domain X of f. In other words, f can undo or "reverse" g, but cannot necessarily be reversed by it.

Every function with a right inverse is necessarily a surjection. The proposition that every surjective function has a right inverse is equivalent to the <a href="Axiom_of_choice" title="Axiom of choice">axiom of choice</a>.

If f : X → Y is surjective and B is a <a href="Subset" title="Subset">subset</a> of Y, then f(f −1(B)) = B. Thus, B can be recovered from its <a href="Preimage" class="mw-redirect" title="Preimage">preimage</a> f −1(B).

For example, in the first illustration in the <a href="#Gallery">gallery</a>, there is some function g such that g(C) = 4. There is also some function f such that f(4) = C. It doesn't matter that g is not unique (it would also work if g(C) equals 3); it only matters that f "reverses" g.

<div class="mw-heading mw-heading3"><h3 id="Surjections_as_epimorphisms">Surjections as epimorphisms</h3></div>

A function f : X → Y is surjective if and only if it is <a href="Right-cancellative" class="mw-redirect" title="Right-cancellative">right-cancellative</a>:<a href="#cite_note-8">[8]</a><a href="#cite_note-9">[9]</a> given any functions g,h : Y → Z, whenever g o f = h o f, then g = h. This property is formulated in terms of functions and their <a href="Function_composition" title="Function composition">composition</a> and can be generalized to the more general notion of the <a href="Morphism" title="Morphism">morphisms</a> of a <a href="Category_(mathematics)" title="Category (mathematics)">category</a> and their composition. Right-cancellative morphisms are called <a href="Epimorphism" title="Epimorphism">epimorphisms</a>. Specifically, surjective functions are precisely the epimorphisms in the <a href="Category_of_sets" title="Category of sets">category of sets</a>. The prefix epi is derived from the Greek preposition ἐπί meaning over, above, on.

Any morphism with a right inverse is an epimorphism, but the converse is not true in general. A right inverse g of a morphism f is called a <a href="Section_(category_theory)" title="Section (category theory)">section</a> of f. A morphism with a right inverse is called a <a href="Split_epimorphism" class="mw-redirect" title="Split epimorphism">split epimorphism</a>.

<div class="mw-heading mw-heading3"><h3 id="Surjections_as_binary_relations">Surjections as binary relations</h3></div>

Any function with domain X and codomain Y can be seen as a <a href="Left-total_relation" class="mw-redirect" title="Left-total relation">left-total</a> and <a href="Right-unique_relation" class="mw-redirect" title="Right-unique relation">right-unique</a> binary relation between X and Y by identifying it with its <a href="Function_graph" class="mw-redirect" title="Function graph">function graph</a>. A surjective function with domain X and codomain Y is then a binary relation between X and Y that is right-unique and both left-total and <a href="Right-total_relation" class="mw-redirect" title="Right-total relation">right-total</a>.

<div class="mw-heading mw-heading3"><h3 id="Cardinality_of_the_domain_of_a_surjection">Cardinality of the domain of a surjection</h3></div>

The <a href="Cardinality" title="Cardinality">cardinality</a> of the domain of a surjective function is greater than or equal to the cardinality of its codomain: If f : X → Y is a surjective function, then X has at least as many elements as Y, in the sense of <a href="Cardinal_number" title="Cardinal number">cardinal numbers</a>. (The proof appeals to the <a href="Axiom_of_choice" title="Axiom of choice">axiom of choice</a> to show that a function

g : Y → X satisfying f(g(y)) = y for all y in Y exists. g is easily seen to be injective, thus the <a href="Cardinal_number#Formal_definition" title="Cardinal number">formal definition</a> of |Y| ≤ |X| is satisfied.)

Specifically, if both X and Y are <a href="Finite_set" title="Finite set">finite</a> with the same number of elements, then f : X → Y is surjective if and only if f is <a href="Injective" class="mw-redirect" title="Injective">injective</a>.

<div class="mw-heading mw-heading3"><h3 id="Composition_and_decomposition">Composition and decomposition</h3></div>

The <a href="Function_composition" title="Function composition">composition</a> of surjective functions is always surjective: If f and g are both surjective, and the codomain of g is equal to the domain of f, then f o g is surjective. Conversely, if f o g is surjective, then f is surjective (but g, the function applied first, need not be). These properties generalize from surjections in the <a href="Category_of_sets" title="Category of sets">category of sets</a> to any <a href="Epimorphism" title="Epimorphism">epimorphisms</a> in any <a href="Category_(mathematics)" title="Category (mathematics)">category</a>.

Any function can be decomposed into a surjection and an <a href="Injective_function" title="Injective function">injection</a>: For any function h : X → Z there exist a surjection f : X → Y and an injection g : Y → Z such that h = g o f. To see this, define Y to be the set of <a href="Preimage" class="mw-redirect" title="Preimage">preimages</a> h−1(z) where z is in h(X). These preimages are <a href="Disjoint_sets" title="Disjoint sets">disjoint</a> and <a href="Partition_of_a_set" title="Partition of a set">partition</a> X. Then f carries each x to the element of Y which contains it, and g carries each element of Y to the point in Z to which h sends its points. Then f is surjective since it is a projection map, and g is injective by definition.

<div class="mw-heading mw-heading3"><h3 id="Induced_surjection_and_induced_bijection">Induced surjection and induced bijection</h3></div>

Any function induces a surjection by restricting its codomain to its range. Any surjective function induces a bijection defined on a <a href="Quotient_set" class="mw-redirect" title="Quotient set">quotient</a> of its domain by collapsing all arguments mapping to a given fixed image. More precisely, every surjection f : A → B can be factored as a projection followed by a bijection as follows. Let A/~ be the <a href="Equivalence_class" title="Equivalence class">equivalence classes</a> of A under the following <a href="Equivalence_relation" title="Equivalence relation">equivalence relation</a>: x ~ y if and only if f(x) = f(y). Equivalently, A/~ is the set of all preimages under f. Let P(~) : A → A/~ be the <a href="Projection_map" class="mw-redirect" title="Projection map">projection map</a> which sends each x in A to its equivalence class [x]~, and let fP : A/~ → B be the well-defined function given by fP([x]~) = f(x). Then f = fP o P(~).

<div class="mw-heading mw-heading2"><h2 id="The_set_of_surjections">The set of surjections</h2></div>

Given fixed finite sets A and B, one can form the set of surjections A ↠ B. The <a href="Cardinality" title="Cardinality">cardinality</a> of this set is one of the twelve aspects of Rota's <a href="Twelvefold_way" title="Twelvefold way">Twelvefold way</a>, and is given by <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle |B|!{\begin{Bmatrix}|A|\\|B|\end{Bmatrix}}}">

</mrow>

</mrow>

<mrow>

<mtr>

<mtd>

</mrow>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

</mrow>

</mrow>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle |B|!{\begin{Bmatrix}|A|\\|B|\end{Bmatrix}}}</annotation>

</semantics>

</math><img src="./2c570b070912f5b4c8de4f467e02d173276ca21d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:11ex; height:6.176ex;" alt="{\textstyle |B|!{\begin{Bmatrix}|A|\\|B|\end{Bmatrix}}}" loading="lazy">, where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle {\begin{Bmatrix}|A|\\|B|\end{Bmatrix}}}">

<mrow>

<mtr>

<mtd>

</mrow>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

</mrow>

</mrow>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle {\begin{Bmatrix}|A|\\|B|\end{Bmatrix}}}</annotation>

</semantics>

</math><img src="./f6d7e1ebeb5522c0f6519865f40aa1d354809c5b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:7.295ex; height:6.176ex;" alt="{\textstyle {\begin{Bmatrix}|A|\\|B|\end{Bmatrix}}}" loading="lazy"> denotes a <a href="Stirling_numbers_of_the_second_kind" title="Stirling numbers of the second kind">Stirling number of the second kind</a>.

<div class="mw-heading mw-heading2"><h2 id="Gallery">Gallery</h2></div>

/* start https://en.wikipedia.org/ */

@media all and (max-width:720px){.mw-parser-output .mod-gallery{width:100%!important}}.mw-parser-output .mod-gallery{display:table}.mw-parser-output .mod-gallery-default{background:transparent;margin-top:4px}.mw-parser-output .mod-gallery-center{margin-left:auto;margin-right:auto}.mw-parser-output .mod-gallery-left{float:left}.mw-parser-output .mod-gallery-right{float:right}.mw-parser-output .mod-gallery-none{float:none}.mw-parser-output .mod-gallery-center .gallery{justify-content:center}.mw-parser-output .mod-gallery-left .gallery{justify-content:left}.mw-parser-output .mod-gallery-right .gallery{justify-content:right}.mw-parser-output .mod-gallery-collapsible{width:100%}.mw-parser-output .mod-gallery .title,.mw-parser-output .mod-gallery .main,.mw-parser-output .mod-gallery .footer{display:table-row}.mw-parser-output .mod-gallery .title>div{display:table-cell;padding:0 4px 4px;text-align:center;font-weight:bold}.mw-parser-output .mod-gallery .main>div{display:table-cell}.mw-parser-output .mod-gallery .gallery.gallery.gallery{line-height:1.35em;display:flex;flex-wrap:wrap;column-gap:4px}.mw-parser-output .mod-gallery .footer>div{display:table-cell;padding:4px;text-align:right;font-size:85%;line-height:1em}.mw-parser-output .mod-gallery .title>div *,.mw-parser-output .mod-gallery .footer>div *{overflow:visible}.mw-parser-output .mod-gallery .gallerybox img{background:none!important}.mw-parser-output .mod-gallery .bordered-images .thumb img{outline:solid var(--background-color-neutral,#eaecf0)1px}.mw-parser-output .mod-gallery .whitebg .thumb{background:var(--background-color-base,#fff)!important}@media screen{html.skin-theme-clientpref-night .mw-parser-output .mod-gallery .bordered-images .thumb img[alt*="\200b \200b \200b "],html.skin-theme-clientpref-night .mw-parser-output .skin-invert-image .mod-gallery .whitebg .thumb.thumb.thumb img{outline:solid #d7d7d7 1px}html.skin-theme-clientpref-night .mw-parser-output .skin-invert-image .mod-gallery .whitebg .thumb.thumb.thumb img{background:none!important}html.skin-theme-clientpref-night .mw-parser-output .mod-gallery .whitebg .thumb img:not([alt*="\200b \200b \200b "]):not([alt*="\200b \200b \200c "]){background:white!important}html.skin-theme-clientpref-night .mw-parser-output .mod-gallery img[alt*="\200b \200b \200b "]{filter:invert(1)hue-rotate(180deg)}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .mod-gallery .bordered-images .thumb img[alt*="\200b \200b \200b "],html.skin-theme-clientpref-os .mw-parser-output .skin-invert-image .mod-gallery .whitebg .thumb.thumb.thumb img{outline:solid #d7d7d7 1px}html.skin-theme-clientpref-os .mw-parser-output .skin-invert-image .mod-gallery .whitebg .thumb.thumb.thumb img{background:none!important}html.skin-theme-clientpref-os .mw-parser-output .mod-gallery .whitebg .thumb img:not([alt*="\200b \200b \200b "]):not([alt*="\200b \200b \200c "]){background:white!important}html.skin-theme-clientpref-os .mw-parser-output .mod-gallery img[alt*="\200b \200b \200b "]{filter:invert(1)hue-rotate(180deg)}}

/* end https://en.wikipedia.org/ */

</style><div class="mod-gallery mod-gallery-default mod-gallery-center"><div class="main"><div><ul class="nochecker bordered-images whitebg gallery mw-gallery-traditional">

<div class="gallerytext">A non-injective surjective function (surjection, not a bijection)</div>

</li>

<div class="gallerytext">An injective surjective function (bijection)</div>

</li>

<div class="gallerytext">An injective non-surjective function (injection, not a bijection)</div>

</li>

<div class="gallerytext">A non-injective non-surjective function (neither a bijection)</div>

</li>

</ul></div></div></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .side-box{margin:4px 0;box-sizing:border-box;border:1px solid #aaa;font-size:88%;line-height:1.25em;background-color:var(--background-color-interactive-subtle,#f8f9fa);display:flow-root}.mw-parser-output .infobox .side-box{font-size:100%}.mw-parser-output .side-box-abovebelow,.mw-parser-output .side-box-text{padding:0.25em 0.9em}.mw-parser-output .side-box-image{padding:2px 0 2px 0.9em;text-align:center}.mw-parser-output .side-box-imageright{padding:2px 0.9em 2px 0;text-align:center}@media(min-width:500px){.mw-parser-output .side-box-flex{display:flex;align-items:center}.mw-parser-output .side-box-text{flex:1;min-width:0}}@media(min-width:720px){.mw-parser-output .side-box{width:238px}.mw-parser-output .side-box-right{clear:right;float:right;margin-left:1em}.mw-parser-output .side-box-left{margin-right:1em}}

/* end https://en.wikipedia.org/ */

</style><style data-mw-deduplicate="TemplateStyles:r1237033735">

/* start https://en.wikipedia.org/ */

@media print{body.ns-0 .mw-parser-output .sistersitebox{display:none!important}}@media screen{html.skin-theme-clientpref-night .mw-parser-output .sistersitebox img[src*="Wiktionary-logo-en-v2.svg"]{background-color:white}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .sistersitebox img[src*="Wiktionary-logo-en-v2.svg"]{background-color:white}}

/* end https://en.wikipedia.org/ */

</style><div class="side-box side-box-right sistersitebox"><style data-mw-deduplicate="TemplateStyles:r1126788409">

/* start https://en.wikipedia.org/ */

.mw-parser-output .plainlist ol,.mw-parser-output .plainlist ul{line-height:inherit;list-style:none;margin:0;padding:0}.mw-parser-output .plainlist ol li,.mw-parser-output .plainlist ul li{margin-bottom:0}

/* end https://en.wikipedia.org/ */

</style>

<div class="side-box-text plainlist">Wikimedia Commons has media related to <a href="https://commons.wikimedia.org/wiki/Category:Surjectivity" class="extiw external" title="commons:Category:Surjectivity">Surjectivity</a>.</div></div>

</div>

<div class="side-box-text plainlist">Look up <a href="https://en.wiktionary.org/wiki/surjective" class="extiw external" title="wiktionary:surjective">surjective</a>, <a href="https://en.wiktionary.org/wiki/surjection" class="extiw external" title="wiktionary:surjection">surjection</a>, or <a href="https://en.wiktionary.org/wiki/onto" class="extiw external" title="wiktionary:onto">onto</a> in Wiktionary, the free dictionary.</div></div>

</div>

<ul><li><a href="Bijection%2C_injection_and_surjection" title="Bijection, injection and surjection">Bijection, injection and surjection</a></li>

<li><a href="Cover_(algebra)" title="Cover (algebra)">Cover (algebra)</a></li>

<li><a href="Covering_map" class="mw-redirect" title="Covering map">Covering map</a></li>

<li><a href="Enumeration" title="Enumeration">Enumeration</a></li>

<li><a href="Fiber_bundle" title="Fiber bundle">Fiber bundle</a></li>

<li><a href="Index_set" title="Index set">Index set</a></li>

<li><a href="Section_(category_theory)" title="Section (category theory)">Section (category theory)</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist reflist-columns references-column-width" style="column-width: 30em;">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://www.mathsisfun.com/sets/injective-surjective-bijective.html">"Injective, Surjective and Bijective"</a>. www.mathsisfun.com. Retrieved 2019-12-07.</cite>

</li>

<li id="cite_note-:1-2">^ <a href="#cite_ref-:1_2-0">a</a> <a href="#cite_ref-:1_2-1">b</a> <cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://brilliant.org/wiki/bijection-injection-and-surjection/">"Bijection, Injection, And Surjection | Brilliant Math & Science Wiki"</a>. brilliant.org. Retrieved 2019-12-07.</cite>

</li>

<li id="cite_note-3"><a href="#cite_ref-3">^</a> <cite id="CITEREFMiller" class="citation cs2">Miller, Jeff, "Injection, Surjection and Bijection", <a rel="nofollow" class="external text" href="http://jeff560.tripod.com/i.html">Earliest Uses of Some of the Words of Mathematics</a>, Tripod</cite>.

</li>

<li id="cite_note-4"><a href="#cite_ref-4">^</a> <cite id="CITEREFMashaal2006" class="citation book cs1">Mashaal, Maurice (2006). <a rel="nofollow" class="external text" href="https://books.google.com/books?id=-CXn6y_1nJ8C&q=injection+surjection+bijection+bourbaki&pg=PA106">Bourbaki</a>. American Mathematical Soc. p. 106. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-8218-3967-6</bdi>.</cite>

</li>

<li id="cite_note-Unicode_Arrows-5"><a href="#cite_ref-Unicode_Arrows_5-0">^</a> <cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://www.unicode.org/charts/PDF/U2190.pdf">"Arrows – Unicode"</a> (PDF). Retrieved 2013-05-11.</cite>

</li>

<li id="cite_note-6"><a href="#cite_ref-6">^</a> <cite id="CITEREFFarlow" class="citation web cs1"><a href="Stanley_Farlow" title="Stanley Farlow">Farlow, S. J.</a> <a rel="nofollow" class="external text" href="http://www.math.umaine.edu/~farlow/sec42.pdf">"Injections, Surjections, and Bijections"</a> (PDF). math.umaine.edu. Retrieved 2019-12-06.</cite>

</li>

<li id="cite_note-7"><a href="#cite_ref-7">^</a> <cite id="CITEREFT._M._Apostol1981" class="citation book cs1">T. M. Apostol (1981). Mathematical Analysis. Addison-Wesley. p. 35.</cite>

</li>

<li id="cite_note-8"><a href="#cite_ref-8">^</a> <cite id="CITEREFGoldblatt2006" class="citation book cs1">Goldblatt, Robert (2006) [1984]. <a rel="nofollow" class="external text" href="http://historical.library.cornell.edu/cgi-bin/cul.math/docviewer?did=Gold010&id=3">Topoi, the Categorial Analysis of Logic</a> (Revised ed.). <a href="Dover_Publications" title="Dover Publications">Dover Publications</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-486-45026-1</bdi>. Retrieved 2009-11-25.</cite>

</li>

<li id="cite_note-9"><a href="#cite_ref-9">^</a> <cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://proofwiki.org/wiki/Surjection_iff_Right_Cancellable">"Surjection iff Right Cancellable"</a>. ProofWiki. Retrieved 2025-06-30.</cite>

</li>

</ol></div>

<div class="mw-heading mw-heading2"><h2 id="Further_reading">Further reading</h2></div>

<ul><li><cite id="bourbaki" class="citation book cs1"><a href="Nicolas_Bourbaki" title="Nicolas Bourbaki">Bourbaki, N.</a> (2004) [1968]. <a rel="nofollow" class="external text" href="https://books.google.com/books?id=7eclBQAAQBAJ&pg=PR1">Theory of Sets</a>. <a href="Elements_of_Mathematics" class="mw-redirect" title="Elements of Mathematics">Elements of Mathematics</a>. Vol. 1. Springer. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F978-3-642-59309-3">10.1007/978-3-642-59309-3</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-540-22525-6</bdi>. <a href="LCCN_(identifier)" class="mw-redirect" title="LCCN (identifier)">LCCN</a> <a rel="nofollow" class="external text" href="https://lccn.loc.gov/2004110815">2004110815</a>.</cite></li></ul>

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbox{box-sizing:border-box;border:1px solid #a2a9b1;width:100%;clear:both;font-size:88%;text-align:center;padding:1px;margin:1em auto 0}.mw-parser-output .navbox .navbox{margin-top:0}.mw-parser-output .navbox+.navbox,.mw-parser-output .navbox+.navbox-styles+.navbox{margin-top:-1px}.mw-parser-output .navbox-inner,.mw-parser-output .navbox-subgroup{width:100%}.mw-parser-output .navbox-group,.mw-parser-output .navbox-title,.mw-parser-output .navbox-abovebelow{padding:0.25em 1em;line-height:1.5em;text-align:center}.mw-parser-output .navbox-group{white-space:nowrap;text-align:right}.mw-parser-output .navbox,.mw-parser-output .navbox-subgroup{background-color:#fdfdfd}.mw-parser-output .navbox-list{line-height:1.5em;border-color:#fdfdfd}.mw-parser-output .navbox-list-with-group{text-align:left;border-left-width:2px;border-left-style:solid}.mw-parser-output tr+tr>.navbox-abovebelow,.mw-parser-output tr+tr>.navbox-group,.mw-parser-output tr+tr>.navbox-image,.mw-parser-output tr+tr>.navbox-list{border-top:2px solid #fdfdfd}.mw-parser-output .navbox-title{background-color:#ccf}.mw-parser-output .navbox-abovebelow,.mw-parser-output .navbox-group,.mw-parser-output .navbox-subgroup .navbox-title{background-color:#ddf}.mw-parser-output .navbox-subgroup .navbox-group,.mw-parser-output .navbox-subgroup .navbox-abovebelow{background-color:#e6e6ff}.mw-parser-output .navbox-even{background-color:#f7f7f7}.mw-parser-output .navbox-odd{background-color:transparent}.mw-parser-output .navbox .hlist td dl,.mw-parser-output .navbox .hlist td ol,.mw-parser-output .navbox .hlist td ul,.mw-parser-output .navbox td.hlist dl,.mw-parser-output .navbox td.hlist ol,.mw-parser-output .navbox td.hlist ul{padding:0.125em 0}.mw-parser-output .navbox .navbar{display:block;font-size:100%}.mw-parser-output .navbox-title .navbar{float:left;text-align:left;margin-right:0.5em}body.skin--responsive .mw-parser-output .navbox-image img{max-width:none!important}@media print{body.ns-0 .mw-parser-output .navbox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style></div><div role="navigation" class="navbox" aria-labelledby="Mathematical_logic344" style="padding:3px"><table class="nowraplinks mw-collapsible mw-collapsed navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><div id="Mathematical_logic344" style="font-size:114%;margin:0 4em"><a href="Mathematical_logic" title="Mathematical logic">Mathematical logic</a></div></th></tr><tr><th scope="row" class="navbox-group" style="width:1%">General</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Axiom" title="Axiom">Axiom</a>

<li><a href="Cardinality" title="Cardinality">Cardinality</a></li>

<li><a href="First-order_logic" title="First-order logic">First-order logic</a></li>

<li><a href="Formal_proof" title="Formal proof">Formal proof</a></li>

<li><a href="Formal_semantics_(logic)" class="mw-redirect" title="Formal semantics (logic)">Formal semantics</a></li>

<li><a href="Foundations_of_mathematics" title="Foundations of mathematics">Foundations of mathematics</a></li>

<li><a href="Information_theory" title="Information theory">Information theory</a></li>

<li><a href="Lemma_(mathematics)" title="Lemma (mathematics)">Lemma</a></li>

<li><a href="Logical_consequence" title="Logical consequence">Logical consequence</a></li>

<li><a href="Structure_(mathematical_logic)" title="Structure (mathematical logic)">Model</a></li>

<li><a href="Theorem" title="Theorem">Theorem</a></li>

<li><a href="Theory_(mathematical_logic)" title="Theory (mathematical logic)">Theory</a></li>

<li><a href="Type_theory" title="Type theory">Type theory</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Theorems (list)  and <a href="Paradoxes_of_set_theory" title="Paradoxes of set theory">paradoxes</a></th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="G%C3%B6del's_completeness_theorem" title="Gödel's completeness theorem">Gödel's completeness</a> and <a href="G%C3%B6del's_incompleteness_theorems" title="Gödel's incompleteness theorems">incompleteness theorems</a></li>

<li><a href="Tarski's_undefinability_theorem" title="Tarski's undefinability theorem">Tarski's undefinability</a></li>

<li><a href="Banach%E2%80%93Tarski_paradox" title="Banach–Tarski paradox">Banach–Tarski paradox</a></li>

<li>Cantor's <a href="Cantor's_theorem" title="Cantor's theorem">theorem,</a> <a href="Cantor's_paradox" title="Cantor's paradox">paradox</a> and <a href="Cantor's_diagonal_argument" title="Cantor's diagonal argument">diagonal argument</a></li>

<li><a href="Compactness_theorem" title="Compactness theorem">Compactness</a></li>

<li><a href="Halting_problem" title="Halting problem">Halting problem</a></li>

<li><a href="Lindstr%C3%B6m's_theorem" title="Lindström's theorem">Lindström's</a></li>

<li><a href="L%C3%B6wenheim%E2%80%93Skolem_theorem" title="Löwenheim–Skolem theorem">Löwenheim–Skolem</a></li>

<li><a href="Russell's_paradox" title="Russell's paradox">Russell's paradox</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Logic" title="Logic">Logics</a></th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><th id="Traditional95" scope="row" class="navbox-group" style="width:1%"><a href="Term_logic" title="Term logic">Traditional</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Classical_logic" title="Classical logic">Classical logic</a></li>

<li><a href="Logical_truth" title="Logical truth">Logical truth</a></li>

<li><a href="Tautology_(logic)" title="Tautology (logic)">Tautology</a></li>

<li><a href="Proposition" title="Proposition">Proposition</a></li>

<li><a href="Inference" title="Inference">Inference</a></li>

<li><a href="Logical_equivalence" title="Logical equivalence">Logical equivalence</a></li>

<li><a href="Consistency" title="Consistency">Consistency</a>

<ul><li><a href="Equiconsistency" title="Equiconsistency">Equiconsistency</a></li></ul></li>

<li><a href="Argument" title="Argument">Argument</a></li>

<li><a href="Soundness" title="Soundness">Soundness</a></li>

<li><a href="Validity_(logic)" title="Validity (logic)">Validity</a></li>

<li><a href="Syllogism" title="Syllogism">Syllogism</a></li>

<li><a href="Square_of_opposition" title="Square of opposition">Square of opposition</a></li>

<li><a href="Venn_diagram" title="Venn diagram">Venn diagram</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Propositional_calculus" class="mw-redirect" title="Propositional calculus">Propositional</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Boolean_algebra" title="Boolean algebra">Boolean algebra</a></li>

<li><a href="Boolean_function" title="Boolean function">Boolean functions</a></li>

<li><a href="Logical_connective" title="Logical connective">Logical connectives</a></li>

<li><a href="Propositional_calculus" class="mw-redirect" title="Propositional calculus">Propositional calculus</a></li>

<li><a href="Propositional_formula" title="Propositional formula">Propositional formula</a></li>

<li><a href="Truth_table" title="Truth table">Truth tables</a></li>

<li><a href="Many-valued_logic" title="Many-valued logic">Many-valued logic</a>

<li><a href="Finite-valued_logic" title="Finite-valued logic">finite</a></li>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Predicate_logic" class="mw-redirect" title="Predicate logic">Predicate</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="First-order_logic" title="First-order logic">First-order</a>

<li><a href="Second-order_logic" title="Second-order logic">Second-order</a>

<ul><li><a href="Monadic_second-order_logic" title="Monadic second-order logic">Monadic</a></li></ul></li>

<li><a href="Higher-order_logic" title="Higher-order logic">Higher-order</a></li>

<li><a href="Fixed-point_logic" title="Fixed-point logic">Fixed-point</a></li>

<li><a href="Quantifier_(logic)" title="Quantifier (logic)">Quantifiers</a></li>

<li><a href="Predicate_(mathematical_logic)" class="mw-redirect" title="Predicate (mathematical logic)">Predicate</a></li>

<li><a href="Monadic_predicate_calculus" title="Monadic predicate calculus">Monadic predicate calculus</a></li></ul>

</div></td></tr></tbody></table><div></div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Set_theory" title="Set theory">Set theory</a></th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><td colspan="2" class="navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Hereditary_set" title="Hereditary set">hereditary</a></li></ul></li>

<li><a href="Class_(set_theory)" title="Class (set theory)">Class</a></li>

<li>(<a href="Urelement" title="Urelement">Ur-</a>)<a href="Element_(mathematics)" title="Element (mathematics)">Element</a></li>

<li><a href="Ordinal_number" title="Ordinal number">Ordinal number</a></li>

<li><a href="Extensionality" title="Extensionality">Extensionality</a></li>

<li><a href="Forcing_(mathematics)" title="Forcing (mathematics)">Forcing</a></li>

<li><a href="Relation_(mathematics)" title="Relation (mathematics)">Relation</a>

<ul><li><a href="Equivalence_relation" title="Equivalence relation">equivalence</a></li>

<li><a href="Partition_of_a_set" title="Partition of a set">partition</a></li></ul></li>

<li>Set operations:

<ul><li><a href="Intersection_(set_theory)" title="Intersection (set theory)">intersection</a></li>

<li><a href="Union_(set_theory)" title="Union (set theory)">union</a></li>

<li><a href="Complement_(set_theory)" title="Complement (set theory)">complement</a></li>

<li><a href="Cartesian_product" title="Cartesian product">Cartesian product</a></li>

<li><a href="Power_set" title="Power set">power set</a></li>

<li><a href="List_of_set_identities_and_relations" title="List of set identities and relations">identities</a></li></ul></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Types of <a href="Set_(mathematics)" title="Set (mathematics)">sets</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Countable_set" title="Countable set">Countable</a></li>

<li><a href="Uncountable_set" title="Uncountable set">Uncountable</a></li>

<li><a href="Empty_set" title="Empty set">Empty</a></li>

<li><a href="Inhabited_set" title="Inhabited set">Inhabited</a></li>

<li><a href="Singleton_(mathematics)" title="Singleton (mathematics)">Singleton</a></li>

<li><a href="Finite_set" title="Finite set">Finite</a></li>

<li><a href="Infinite_set" title="Infinite set">Infinite</a></li>

<li><a href="Transitive_set" title="Transitive set">Transitive</a></li>

<li><a href="Ultrafilter_(set_theory)" class="mw-redirect" title="Ultrafilter (set theory)">Ultrafilter</a></li>

<li><a href="Recursive_set" class="mw-redirect" title="Recursive set">Recursive</a></li>

<li><a href="Fuzzy_set" title="Fuzzy set">Fuzzy</a></li>

<li><a href="Universal_set" title="Universal set">Universal</a></li>

<li><a href="Universe_(mathematics)" title="Universe (mathematics)">Universe</a>

<ul><li><a href="Constructible_universe" title="Constructible universe">constructible</a></li>

<li><a href="Grothendieck_universe" title="Grothendieck universe">Grothendieck</a></li>

<li><a href="Von_Neumann_universe" title="Von Neumann universe">Von Neumann</a></li></ul></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Map_(mathematics)" title="Map (mathematics)">Maps</a> and <a href="Cardinality" title="Cardinality">cardinality</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Function_(mathematics)" title="Function (mathematics)">Function</a>/<a href="Map_(mathematics)" title="Map (mathematics)">Map</a>

<ul><li><a href="Domain_of_a_function" title="Domain of a function">domain</a></li>

<li><a href="Codomain" title="Codomain">codomain</a></li>

<li><a href="Image_(mathematics)" title="Image (mathematics)">image</a></li></ul></li>

<li><a href="Injective_function" title="Injective function">In</a>//<a href="Bijection" title="Bijection">Bi</a>-jection</li>

<li><a href="Schr%C3%B6der%E2%80%93Bernstein_theorem" title="Schröder–Bernstein theorem">Schröder–Bernstein theorem</a></li>

<li><a href="Isomorphism" title="Isomorphism">Isomorphism</a></li>

<li><a href="G%C3%B6del_numbering" title="Gödel numbering">Gödel numbering</a></li>

<li><a href="Enumeration" title="Enumeration">Enumeration</a></li>

<li><a href="Large_cardinal" title="Large cardinal">Large cardinal</a>

<ul><li><a href="Inaccessible_cardinal" title="Inaccessible cardinal">inaccessible</a></li></ul></li>

<li><a href="Aleph_number" title="Aleph number">Aleph number</a></li>

<li><a href="Operation_(mathematics)" title="Operation (mathematics)">Operation</a>

<ul><li><a href="Binary_operation" title="Binary operation">binary</a></li></ul></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Set theories</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Zermelo%E2%80%93Fraenkel_set_theory" title="Zermelo–Fraenkel set theory">Zermelo–Fraenkel</a>

<ul><li><a href="Axiom_of_choice" title="Axiom of choice">axiom of choice</a></li>

<li><a href="Continuum_hypothesis" title="Continuum hypothesis">continuum hypothesis</a></li></ul></li>

<li><a href="General_set_theory" title="General set theory">General</a></li>

<li><a href="Kripke%E2%80%93Platek_set_theory" title="Kripke–Platek set theory">Kripke–Platek</a></li>

<li><a href="Morse%E2%80%93Kelley_set_theory" title="Morse–Kelley set theory">Morse–Kelley</a></li>

<li><a href="Naive_set_theory" title="Naive set theory">Naive</a></li>

<li><a href="New_Foundations" title="New Foundations">New Foundations</a></li>

<li><a href="Tarski%E2%80%93Grothendieck_set_theory" title="Tarski–Grothendieck set theory">Tarski–Grothendieck</a></li>

<li><a href="Von_Neumann%E2%80%93Bernays%E2%80%93G%C3%B6del_set_theory" title="Von Neumann–Bernays–Gödel set theory">Von Neumann–Bernays–Gödel</a></li>

<li><a href="Ackermann_set_theory" title="Ackermann set theory">Ackermann</a></li>

<li><a href="Constructive_set_theory" title="Constructive set theory">Constructive</a></li></ul>

</div></td></tr></tbody></table><div></div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Formal_system" title="Formal system">Formal systems</a> (<a href="List_of_formal_systems" title="List of formal systems">list</a>), <a href="Formal_language" title="Formal language">language</a> and <a href="Syntax_(logic)" title="Syntax (logic)">syntax</a></th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><td colspan="2" class="navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Alphabet_(formal_languages)" title="Alphabet (formal languages)">Alphabet</a></li>

<li><a href="Arity" title="Arity">Arity</a></li>

<li><a href="Automata_theory" title="Automata theory">Automata</a></li>

<li><a href="Axiom_schema" title="Axiom schema">Axiom schema</a></li>

<li><a href="Expression_(mathematics)" title="Expression (mathematics)">Expression</a>

<ul><li><a href="Ground_expression" title="Ground expression">ground</a></li></ul></li>

<li><a href="Extension_by_new_constant_and_function_names" title="Extension by new constant and function names">Extension</a>

<ul><li><a href="Extension_by_definitions" class="mw-redirect" title="Extension by definitions">by definition</a></li>

<li><a href="Conservative_extension" title="Conservative extension">conservative</a></li></ul></li>

<li><a href="Finitary_relation" title="Finitary relation">Relation</a></li>

<li><a href="Formation_rule" title="Formation rule">Formation rule</a></li>

<li><a href="Formal_grammar" title="Formal grammar">Grammar</a></li>

<li><a href="Well-formed_formula" title="Well-formed formula">Formula</a>

<ul><li><a href="Atomic_formula" title="Atomic formula">atomic</a></li>

<li><a href="Sentence_(mathematical_logic)" title="Sentence (mathematical logic)">closed</a></li>

<li><a href="Ground_formula" class="mw-redirect" title="Ground formula">ground</a></li>

<li><a href="Free_variables_and_bound_variables" title="Free variables and bound variables">Free/bound variable</a></li>

<li><a href="Formal_language" title="Formal language">Language</a></li>

<li><a href="Metalanguage" title="Metalanguage">Metalanguage</a></li>

<li><a href="Logical_connective" title="Logical connective">Logical connective</a>

<li><a href="Predicate_(mathematical_logic)" class="mw-redirect" title="Predicate (mathematical logic)">Predicate</a>

<ul><li><a href="Functional_predicate" title="Functional predicate">functional</a></li>

<li><a href="Predicate_variable" title="Predicate variable">variable</a></li>

<li><a href="Propositional_variable" title="Propositional variable">propositional variable</a></li></ul></li>

<li><a href="Formal_proof" title="Formal proof">Proof</a></li>

<li><a href="Quantifier_(logic)" title="Quantifier (logic)">Quantifier</a>

<li><a href="Sentence_(mathematical_logic)" title="Sentence (mathematical logic)">Sentence</a>

<ul><li><a href="Atomic_sentence" title="Atomic sentence">atomic</a></li>

<li><a href="Spectrum_of_a_sentence" title="Spectrum of a sentence">spectrum</a></li></ul></li>

<li><a href="Signature_(logic)" title="Signature (logic)">Signature</a></li>

<li><a href="String_(formal_languages)" class="mw-redirect" title="String (formal languages)">String</a></li>

<li><a href="Substitution_(logic)" title="Substitution (logic)">Substitution</a></li>

<li><a href="Symbol_(formal)" title="Symbol (formal)">Symbol</a>

<ul><li><a href="Uninterpreted_function" title="Uninterpreted function">function</a></li>

<li><a href="Logical_constant" title="Logical constant">logical/constant</a></li>

<li><a href="Non-logical_symbol" title="Non-logical symbol">non-logical</a></li>

<li><a href="Variable_(mathematics)" title="Variable (mathematics)">variable</a></li></ul></li>

<li><a href="Theory_(mathematical_logic)" title="Theory (mathematical logic)">Theory</a>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Example <a href="Axiomatic_system" title="Axiomatic system">axiomatic systems</a> (<a href="List_of_first-order_theories" title="List of first-order theories">list</a>)</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li>of <a href="True_arithmetic" title="True arithmetic">arithmetic</a>:

<ul><li><a href="Peano_axioms" title="Peano axioms">Peano</a></li>

<li><a href="Second-order_arithmetic" title="Second-order arithmetic">second-order</a></li>

<li><a href="Elementary_function_arithmetic" title="Elementary function arithmetic">elementary function</a></li>

<li><a href="Primitive_recursive_arithmetic" title="Primitive recursive arithmetic">primitive recursive</a></li>

<li><a href="Robinson_arithmetic" title="Robinson arithmetic">Robinson</a></li>

<li><a href="Skolem_arithmetic" title="Skolem arithmetic">Skolem</a></li></ul></li>

<li>of the <a href="Construction_of_the_real_numbers" title="Construction of the real numbers">real numbers</a>

<ul><li><a href="Tarski's_axiomatization_of_the_reals" title="Tarski's axiomatization of the reals">Tarski's axiomatization</a></li></ul></li>

<li>of <a href="Axiomatization_of_Boolean_algebras" class="mw-redirect" title="Axiomatization of Boolean algebras">Boolean algebras</a>

<ul><li><a href="Boolean_algebras_canonically_defined" title="Boolean algebras canonically defined">canonical</a></li>

<li><a href="Minimal_axioms_for_Boolean_algebra" title="Minimal axioms for Boolean algebra">minimal axioms</a></li></ul></li>

<li>of <a href="Foundations_of_geometry" title="Foundations of geometry">geometry</a>:

<ul><li><a href="Euclidean_geometry" title="Euclidean geometry">Euclidean</a>:

<ul><li><a href="Euclid's_Elements" title="Euclid's Elements">Elements</a></li>

<li><a href="Hilbert's_axioms" title="Hilbert's axioms">Hilbert's</a></li>

<li><a href="Tarski's_axioms" title="Tarski's axioms">Tarski's</a></li></ul></li>

<li><a href="Non-Euclidean_geometry" title="Non-Euclidean geometry">non-Euclidean</a></li></ul></li></ul>

<ul><li><a href="Principia_Mathematica" title="Principia Mathematica">Principia Mathematica</a></li></ul>

</div></td></tr></tbody></table><div></div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Proof_theory" title="Proof theory">Proof theory</a></th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Formal_proof" title="Formal proof">Formal proof</a></li>

<li><a href="Natural_deduction" title="Natural deduction">Natural deduction</a></li>

<li><a href="Logical_consequence" title="Logical consequence">Logical consequence</a></li>

<li><a href="Rule_of_inference" title="Rule of inference">Rule of inference</a></li>

<li><a href="Sequent_calculus" title="Sequent calculus">Sequent calculus</a></li>

<li><a href="Theorem" title="Theorem">Theorem</a></li>

<li><a href="Formal_system" title="Formal system">Systems</a>

<ul><li><a href="Axiomatic_system" title="Axiomatic system">axiomatic</a></li>

<li><a href="Deductive_system" class="mw-redirect" title="Deductive system">deductive</a></li>

<li><a href="Hilbert_system" title="Hilbert system">Hilbert</a>

<li><a href="Complete_theory" title="Complete theory">Complete theory</a></li>

<li><a href="Independence_(mathematical_logic)" title="Independence (mathematical logic)">Independence</a> (<a href="List_of_statements_independent_of_ZFC" title="List of statements independent of ZFC">from ZFC</a>)</li>

<li><a href="Proof_of_impossibility" title="Proof of impossibility">Proof of impossibility</a></li>

<li><a href="Ordinal_analysis" title="Ordinal analysis">Ordinal analysis</a></li>

<li><a href="Reverse_mathematics" title="Reverse mathematics">Reverse mathematics</a></li>

<li><a href="Self-verifying_theories" title="Self-verifying theories">Self-verifying theories</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Model_theory" title="Model theory">Model theory</a></th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Interpretation_(logic)" title="Interpretation (logic)">Interpretation</a>

<ul><li><a href="Interpretation_function" class="mw-redirect" title="Interpretation function">function</a></li>

<li><a href="Interpretation_(model_theory)" title="Interpretation (model theory)">of models</a></li></ul></li>

<li><a href="Structure_(mathematical_logic)" title="Structure (mathematical logic)">Model</a>

<ul><li><a href="Elementary_equivalence" title="Elementary equivalence">equivalence</a></li>

<li><a href="Finite_model_theory" title="Finite model theory">finite</a></li>

<li><a href="Saturated_model" title="Saturated model">saturated</a></li>

<li><a href="Spectrum_of_a_theory" title="Spectrum of a theory">spectrum</a></li>

<li><a href="Substructure_(mathematics)" title="Substructure (mathematics)">submodel</a></li></ul></li>

<li><a href="Non-standard_model" title="Non-standard model">Non-standard model</a>

<ul><li><a href="Non-standard_model_of_arithmetic" title="Non-standard model of arithmetic">of arithmetic</a></li></ul></li>

<li><a href="Diagram_(mathematical_logic)" title="Diagram (mathematical logic)">Diagram</a>

<ul><li><a href="Elementary_diagram" title="Elementary diagram">elementary</a></li></ul></li>

<li><a href="Categorical_theory" title="Categorical theory">Categorical theory</a></li>

<li><a href="Model_complete_theory" title="Model complete theory">Model complete theory</a></li>

<li><a href="Satisfiability" title="Satisfiability">Satisfiability</a></li>

<li><a href="Semantics_of_logic" title="Semantics of logic">Semantics of logic</a></li>

<li><a href="Strength_(mathematical_logic)" title="Strength (mathematical logic)">Strength</a></li>

<li><a href="Theories_of_truth" class="mw-redirect" title="Theories of truth">Theories of truth</a>

<ul><li><a href="Semantic_theory_of_truth" title="Semantic theory of truth">semantic</a></li>

<li><a href="Tarski's_theory_of_truth" class="mw-redirect" title="Tarski's theory of truth">Tarski's</a></li>

<li><a href="Kripke's_theory_of_truth" class="mw-redirect" title="Kripke's theory of truth">Kripke's</a></li></ul></li>

<li><a href="T-schema" title="T-schema">T-schema</a></li>

<li><a href="Transfer_principle" title="Transfer principle">Transfer principle</a></li>

<li><a href="Truth_predicate" title="Truth predicate">Truth predicate</a></li>

<li><a href="Truth_value" title="Truth value">Truth value</a></li>

<li><a href="Ultraproduct" title="Ultraproduct">Ultraproduct</a></li>

<li><a href="Validity_(logic)" title="Validity (logic)">Validity</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Computability_theory" title="Computability theory">Computability theory</a></th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Church_encoding" title="Church encoding">Church encoding</a></li>

<li><a href="Church%E2%80%93Turing_thesis" title="Church–Turing thesis">Church–Turing thesis</a></li>

<li><a href="Computably_enumerable_set" title="Computably enumerable set">Computably enumerable</a></li>

<li><a href="Computable_function" title="Computable function">Computable function</a></li>

<li><a href="Computable_set" title="Computable set">Computable set</a></li>

<li><a href="Decision_problem" title="Decision problem">Decision problem</a>

<ul><li><a href="Decidability_(logic)" title="Decidability (logic)">decidable</a></li>

<li><a href="Undecidable_problem" title="Undecidable problem">undecidable</a></li>

<li><a href="P_versus_NP_problem" title="P versus NP problem">P versus NP problem</a></li></ul></li>

<li><a href="Kolmogorov_complexity" title="Kolmogorov complexity">Kolmogorov complexity</a></li>

<li><a href="Lambda_calculus" title="Lambda calculus">Lambda calculus</a></li>

<li><a href="Primitive_recursive_function" title="Primitive recursive function">Primitive recursive function</a></li>

<li><a href="Recursion" title="Recursion">Recursion</a></li>

<li><a href="Recursive_set" class="mw-redirect" title="Recursive set">Recursive set</a></li>

<li><a href="Turing_machine" title="Turing machine">Turing machine</a></li>

<li><a href="Type_theory" title="Type theory">Type theory</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Related</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Abstract_logic" title="Abstract logic">Abstract logic</a></li>

<li><a href="Algebraic_logic" title="Algebraic logic">Algebraic logic</a></li>

<li><a href="Automated_theorem_proving" title="Automated theorem proving">Automated theorem proving</a></li>

<li><a href="Category_theory" title="Category theory">Category theory</a></li>

<li><a href="Concrete_category" title="Concrete category">Concrete</a>/<a href="Category_(mathematics)" title="Category (mathematics)">Abstract category</a></li>

<li><a href="Category_of_sets" title="Category of sets">Category of sets</a></li>

<li><a href="History_of_logic" title="History of logic">History of logic</a></li>

<li><a href="History_of_mathematical_logic" class="mw-redirect" title="History of mathematical logic">History of mathematical logic</a>

<ul><li><a href="Timeline_of_mathematical_logic" title="Timeline of mathematical logic">timeline</a></li></ul></li>

<li><a href="Logicism" title="Logicism">Logicism</a></li>

<li><a href="Mathematical_object" title="Mathematical object">Mathematical object</a></li>

<li><a href="Philosophy_of_mathematics" title="Philosophy of mathematics">Philosophy of mathematics</a></li>

<li><a href="Supertask" title="Supertask">Supertask</a></li></ul>

</div></td></tr><tr><td class="navbox-abovebelow" colspan="2"><div> <a href="Portal%3AMathematics" title="Portal:Mathematics">Mathematics portal</a></div></td></tr></tbody></table></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-07-16" href="https://en.wikipedia.org/wiki/?title=Surjective_function&oldid=1300813553">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>